package datastructure.hash;

import java.util.*;

public class MyRandomizedSet {

    private final List<Integer>[] nodes;
    private final List<Integer> values;

    public MyRandomizedSet() {
        nodes = new List[10000];
        values = new ArrayList<>();
    }

    public boolean insert(int val) {
        int hashIndex = hash(val);
        List<Integer> list = nodes[hashIndex];
        if (list == null) {
            values.add(val);
            int index = values.size()-1;
            list = new LinkedList<>();
            list.add(index);
            nodes[hashIndex] = list;
            return true;
        } else {
            for (Integer i : list) {
                if (values.get(i) == val) {
                    return false;
                }
            }
            values.add(val);
            int index = values.size() - 1;
            list.add(index);
            return true;
        }
    }

    public boolean remove(int val) {
        int hashIndex = hash(val);
        List<Integer> node = nodes[hashIndex];
        if (node == null) {
            return false;
        } else {
            boolean flag = false;
            Iterator<Integer> iterator = node.iterator();
            while (iterator.hasNext()) {
                int next = iterator.next();
                if (values.get(next) == val) {
                    iterator.remove();
                    if (next != values.size() - 1) {
                        values.set(next,values.get(values.size()-1));
                        Integer last = values.get(values.size()-1);
                        int lastHashIndex = hash(last);
                        List<Integer> lastNode = nodes[lastHashIndex];
                        lastNode.set(lastNode.indexOf(values.size()-1), next);
                    }
                    values.remove(values.size()-1);
                    flag = true;
                }
            }
            if (flag){
                if (node.isEmpty()){
                    nodes[hashIndex] = null;
                }
                return true;
            }else {
                return false;
            }
        }
    }

    public int getRandom() {
        Random random = new Random();
        return values.get(random.nextInt(values.size()));
    }

    private int hash(int key){
        if (key < 0) {
            key = -key;
        }
        return key % nodes.length;
    }

    public static void main(String[] args) {
        MyRandomizedSet set = new MyRandomizedSet();
        System.out.println(set.insert(-1));
        System.out.println(set.remove(-2));
        System.out.println(set.insert(-2));
        System.out.println(set.getRandom());
        System.out.println(set.remove(-1));
        System.out.println(set.insert(-2));
        System.out.println(set.getRandom());

        System.out.println(set.remove(0));
        System.out.println(set.insert(0));
        System.out.println(set.getRandom());
    }
}
